In many contexts, it may be necessary to find a closest point in a database to a given query point. For example, the data in the database may be represented as high dimensional points that reside in a metric space (a space such that distances between members are defined). The closest point to the given query point is defined based on a distance function. In some examples, a single closest point to the query point may be found and, in other examples, a number of closest points may be found. For example, the closest point or nearest neighbor (NN) problem may be generalized as a k-NN search where the goal is to find the k nearest neighbors to a given query point. In some applications, it may be sufficient to determine approximate nearest neighbors instead of guaranteeing the actual nearest neighbors in every case particularly when such techniques may offer the advantages of speed and/or a guaranteed maximum search time or the like. Such techniques may be characterized as approximate nearest neighbor (A-NN) searches.
A variety of techniques have been used and proposed for performing approximate nearest neighbor searches. The quality and usefulness of such techniques may be evaluated based on the time complexity of the search technique and the space complexity of the database or data structure being searched. Example techniques include KD (k-dimensional) trees and metric trees (e.g., vantage point trees). Such techniques provide data structures for organizing points in a multidimensional space that are useful for searching a multidimensional query point efficiently by eliminating large portions of the search space.
It may be advantageous to provide fast, efficient, and high quality searching for databases or data structures of multidimensional points. It is with respect to these and other considerations that the present improvements have been needed. Such improvements may become critical as the desire to provide database searching for nearest neighbors becomes more widespread.